/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package uloha3;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class VyriesBandB implements BatohAlgoritmus {

    public List<Batoh> zoznamInstancii;
    PriorityQueue<Konfiguracia> expandovaneKonfiguracie;
    static int najlepsiaCena ;

    VyriesBandB(List<Batoh> zoznamInstancii) {
        this.zoznamInstancii = zoznamInstancii;
    }

    private void rekurzivnePrechadzajStavovyPriestor(Batoh b, int[] aktualnaKonfiguracia, int[] najlepsiaKonfiguracia, int []najlepsiaCena, int pocetPevnych) {

        if (!jePodmienkaSplnena(b, aktualnaKonfiguracia)) {
            return;
        }
        if ((getMaxMoznaCena(b, aktualnaKonfiguracia, pocetPevnych)) < najlepsiaCena[0]) {
            return;
        }


        if (pocetPevnych == (b.pocetVeciVbatohu - 1)) {
            int poslednaCena = getMaxMoznaCena(b, aktualnaKonfiguracia, pocetPevnych);
            if (poslednaCena > najlepsiaCena[0]) {
                for (int i = 0; i < najlepsiaKonfiguracia.length; i++) {
                    najlepsiaKonfiguracia[i] = aktualnaKonfiguracia[i];
                }
                najlepsiaCena[0] = poslednaCena;
            }
            return;
        }

        //ak je to konfiguracia niekde uprostred , zvysim pocet pevnych - expandujem a
        // rekurzivne volam dalsie

        pocetPevnych++;
        aktualnaKonfiguracia[pocetPevnych] = 0;
        int[] poleSnulou = new int[aktualnaKonfiguracia.length];
        for (int i = 0; i < poleSnulou.length; i++) {
            poleSnulou[i] = aktualnaKonfiguracia[i];
        }
        int cenaSnulou = getMaxMoznaCena(b, poleSnulou, pocetPevnych);

        aktualnaKonfiguracia[pocetPevnych] = 1;
        int[] poleSjednotkou = new int[aktualnaKonfiguracia.length];
        for (int i = 0; i < poleSjednotkou.length; i++) {
            poleSjednotkou[i] = aktualnaKonfiguracia[i];
        }
        int cenaSjednotkou = getMaxMoznaCena(b, poleSjednotkou, pocetPevnych);

        if (cenaSjednotkou > cenaSnulou) {
            rekurzivnePrechadzajStavovyPriestor(b, poleSjednotkou, najlepsiaKonfiguracia, najlepsiaCena, pocetPevnych);
            rekurzivnePrechadzajStavovyPriestor(b, poleSnulou, najlepsiaKonfiguracia, najlepsiaCena, pocetPevnych);
        } else {
            rekurzivnePrechadzajStavovyPriestor(b, poleSnulou, najlepsiaKonfiguracia, najlepsiaCena, pocetPevnych);
            rekurzivnePrechadzajStavovyPriestor(b, poleSjednotkou, najlepsiaKonfiguracia, najlepsiaCena, pocetPevnych);
        }
    }

    private int getMaxMoznaCena(Batoh b, int[] aktualnaKonfiguracia, int pocetPevnych) {
        int maxMoznaCena = 0;
        for (int i = 0; i <= pocetPevnych; i++) {
            maxMoznaCena += (aktualnaKonfiguracia[i]) * (b.zoznamVeci.get(i).cenaVeci);
        }
        for (int j = pocetPevnych + 1; j < aktualnaKonfiguracia.length; j++) {
            maxMoznaCena += (b.zoznamVeci.get(j).cenaVeci);
        }
        return maxMoznaCena;
    }

    private boolean jePodmienkaSplnena(Batoh b, int[] aktualnaKonfiguracia) {
        int hmotnost = 0;
        for (int i = 0; i < aktualnaKonfiguracia.length; i++) {
            hmotnost += aktualnaKonfiguracia[i] * b.zoznamVeci.get(i).hmotnostVeci;
        }
        return (hmotnost <= b.maxHmotnost);
    }

    public String vyriesProblemBatohu() {
    StringBuilder riesenie = new StringBuilder();
        for (Batoh aktualnaInstancia : zoznamInstancii) {
            int[] konfiguracia = new int[aktualnaInstancia.pocetVeciVbatohu];
            int[] najKonfiguracia = new int[aktualnaInstancia.pocetVeciVbatohu];

            Arrays.fill(konfiguracia, 0);
           // Arrays.fill(najKonfiguracia, 0);

            najlepsiaCena = -1;
            int pocetPevnych = -1;
            int [] najlepsiaCena = new int[1];
            najlepsiaCena[0] = -1;
            rekurzivnePrechadzajStavovyPriestor(aktualnaInstancia, konfiguracia, najKonfiguracia, najlepsiaCena, pocetPevnych);
            riesenie.append(aktualnaInstancia.cisloInstancie + " " + aktualnaInstancia.pocetVeciVbatohu + " " + najlepsiaCena[0]+" ");
            for (int i = 0; i < najKonfiguracia.length; i++) {
                riesenie.append( najKonfiguracia[i]+ " " );

            }
            riesenie.append("\n");
            
         }
        System.out.println(riesenie.toString());
        return riesenie.toString();
    }
}
